//题目:
// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
#include<iostream>
#include<vector>

using namespace std;
//代码:
class Solution 
{
    string arr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    string str;
    vector<string> v;
public:
    void dfs(const string& digits,int level)
    {
        if(str.size()==digits.size()){
            v.push_back(str);
            return;
        }

        for(int i=0;i<arr[digits[level]-'0'].size();i++)
        {
            str+=arr[digits[level]-'0'][i];
            dfs(digits,level+1);
            //回溯：从本层挑选下一个元素前，需要将原先的元素丢弃
            str.pop_back();
        }

    }
    vector<string> letterCombinations(string digits) 
    {
        if(digits.size()==0)return v;

        dfs(digits,0);
        return v;
    }
};